package com.yulan.subString;

import org.junit.Test;

/**
 * 14. 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 */
public class LeetCode_14 {
    /**
     * 前缀树
     */
    private class TrieTree{
        /**
         * 树的子节点
         */
        private class TrieNode{
            int charCount;
            TrieNode[] children;

            public TrieNode(){
                charCount = 0;
                children = new TrieNode[26];
            }
        }

        //树的根节点
        private TrieNode root ;

        public TrieTree(){
            root = new TrieNode();
        }

        public void insert(String word){
            TrieNode pNode = root;
            for(int i = 0; i<word.length(); i++){
                int index = (int)(word.charAt(i) - 'a');
                if(pNode.children[index] == null){
                    pNode.children[index] = new TrieNode();
                    pNode.charCount++;
                }
                pNode = pNode.children[index];
            }
            pNode.charCount++;
        }

        public boolean allStartWith(String prefix){
            TrieNode p = root;
            for(int i = 0; i<prefix.length(); i++){
                if(p.charCount > 1) return  false;//尿分叉，直接返回
                int index = prefix.charAt(i) - 'a';
                //如果没有尿分叉，并且检查到空，并且前缀还没用完，说明这个前缀不行
                if(p.children[index] == null) return false;
                p = p.children[index];
            }
            return true;
        }

    }




    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0)
            return "";
        int len = strs[0].length();
        TrieTree tree = new TrieTree();
        for(String str:strs){
           tree.insert(str);
        }

       int l = 0, r = len;
       while(l<=r){
           int mid = (l+r)>>>1;
           if(tree.allStartWith(strs[0].substring(0,mid))){
               l = mid+1;
           }else{
               r = mid-1;
           }
       }
       return strs[0].substring(0,r);
    }

    public String longestCommonPrefix2(String[] strs) {
        if(strs == null || strs.length == 0)
            return "";
        int len = strs[0].length();
        int count = strs.length;
        for(int i = 0;i<len;i++){
            char c = strs[0].charAt(i);
            for(int j =  1;j<count;j++){
                if( i == strs[j].length() || strs[j].charAt(i) != c ){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }

    @Test
    public void test(){
        String[] strs = {"dog","racecar","car"};
        System.out.println(longestCommonPrefix(strs));
    }
}
